#pragma once

#include<iostream>
using namespace std;
#include<vector>
#include<map>

// W = weight 权值
template<class V,class W,W Max_W = INT_MAX,bool Direction = false>
class Graph
{
public:
	Graph(const V* a, size_t n)
	{
		_matrix.resize(n);
		for (size_t i = 0; i < n; ++i)
		{
			_vertex.push_back(a[i]);
			_indexMap[a[i]] = i;
			_matrix[i].resize(n, Max_W);
		}
	}

	size_t GetVertexIndex(const V& v)
	{
		auto it = _indexMap.find(v);
		if (it != _indexMap.end())
		{
			return it->second;
		}
		else
		{
			throw invalid_argument("顶点不存在");
			return -1;
		}
	}


	void AddEdge(const V& src, const V&dst, const W& w)
	{
		size_t srci = GetVertexIndex(src);
		size_t dsti = GetVertexIndex(dst);
		_matrix[srci][dsti] = w;
		if (Direction == false)
		{
			_matrix[dsti][srci] = w;
		}
	}

	void Print()
	{
		cout << "  ";
		for (size_t i = 0; i < _vertex.size(); ++i)
		{
			cout << _vertex[i] << " ";
		}
		cout << endl;
		for (size_t i = 0; i < _vertex.size(); ++i)
		{
			cout << _vertex[i] << " ";
			for (size_t j = 0; j < _vertex.size(); ++j)
			{
				if (_matrix[i][j] != Max_W)
					cout << _matrix[i][j] << " ";
				else
					cout << "#" << " ";
			}
			cout << endl;
		}
	}

private:
	vector<V> _vertex; // 顶点集合
	map<V, int> _indexMap; // 顶点映射下标 
	vector<vector<W>> _matrix; // 邻接矩阵
};
